#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <string.h>
#define MaxSons 3
#define MaxSize 66
typedef char ElemType;
typedef struct node
{
    ElemType data[15];          //结点的值
    struct node *sons[MaxSons]; //指向孩子结点
} TSonNode;                     //孩子链存储结构中的结点类型
typedef struct
{
    char N[15];
    char n[15];
} array;
//读取文件内容到数组R中
void ReadFile(array R[], FILE *fp, int &n)
{
    while ((fscanf(fp, "%s", R[n].N)) != EOF && (fscanf(fp, "%s", R[n].n)) != EOF)
        n++;
}
//创建一颗树
TSonNode *CreateTree(char str[], array R[], int n)
{
    TSonNode *t;
    int k, i = 0, j = 0;
    t = (TSonNode *)malloc(sizeof(TSonNode));
    strcpy(t->data, str);
    for (k = 0; k < MaxSons; k++)
        t->sons[k] = NULL;
    while (i < n)
    {
        if (strcmp(R[i].N, str) == 0)
        {
            t->sons[j] = CreateTree(R[i].n, R, n);
            j++;
        }
        i++;
    }
    return t;
}
//输出树(孩子链存储结构)
void DispTree(TSonNode *t)
{
    int i = 0;
    if (t == NULL)
        printf("此树为空树!\n");
    else
    {
        printf("%s", t->data);
        if (t->sons[i] != NULL) //若t结点至少有一个孩子
        {
            printf("(");
            for (i = 0; i < MaxSons; i++)
            {
                DispTree(t->sons[i]);
                if (t->sons[i + 1] != NULL)
                    printf(",");
                else
                    break;
            }
            printf(")");
        }
    }
}
//销毁树
void DestroyTree(TSonNode *t)
{
    if (t == NULL)
        printf("此树为空树!\n");
    else
    {
        for (int i = 0; i < MaxSons; i++)
        {
            if (t->sons[i] != NULL)
                DestroyTree(t->sons[i]);
            else
                break;
        }
        free(t);
    }
}
//查找某一结点
TSonNode *FindNode(TSonNode *t, char str[])
{
    TSonNode *p;
    if (t == NULL)
        return NULL;
    else
    {
        if (strcmp(t->data, str) == 0)
            return t;
        else
        {
            for (int i = 0; i < MaxSons; i++)
            {
                if (t->sons[i] != NULL)
                {
                    p = FindNode(t->sons[i], str);
                    if (p != NULL)
                        return p;
                }
            }
            return NULL;
        }
    }
}
//求某一结点的孩子个数
int ChildCount(TSonNode *p)
{
    int count = 0;
    for (int i = 0; i < MaxSons; i++)
    {
        if (p->sons[i] != NULL)
            count++;
        else
            break;
    }
    return count;
}
//求某棵树中的叶子结点数
//本例中，叶子结点数等于班级数,一个叶子结点对应一个班级
int LeafCount(TSonNode *p)
{
    int count = 0;
    if (p == NULL)
        return 0;
    else
    {
        if (p->sons[0] == NULL)
            count++;
        else
        {
            for (int i = 0; i < MaxSons; i++)
            {
                if (p->sons[i] != NULL)
                    count = count + LeafCount(p->sons[i]);
                else
                    break;
            }
        }
    }
    return count;
}
//求某棵树的叶子结点值的和
int LeafSumOfvalue(TSonNode *p)
{
    int sum = 0;
    if (p == NULL)
        return 0;
    else
    {
        if (p->sons[0] == NULL)
            return atoi(p->data);
        else
        {
            for (int i = 0; i < MaxSons; i++)
            {
                if (p->sons[i] != NULL)
                    sum += LeafSumOfvalue(p->sons[i]);
                else
                    break;
            }
        }
    }
    return sum;
}

int main()
{
    int n = 0;
    TSonNode *t;
    array R[MaxSize];
    FILE *fp;
    if ((fp = fopen("table.txt", "r")) == NULL) //以只读方式打开table.txt文件
    {
        printf("error!cannot open the file!");
        exit(1);
    }
    printf("读取文件内容存入数组R中\n");
    ReadFile(R, fp, n);
    printf("输出数组R:\n");
    for (int i = 0; i < n; i++)
        printf("%s %s\n", R[i].N, R[i].n); //输出R数组查看是否读取正确
    printf("\n由数组R创建树T,");
    t = CreateTree(R[0].N, R, n); //创建一颗树
    printf("由括号表示输出树T:\n");
    DispTree(t);
    char str[10];
    printf("\n请输入学院名:");
    scanf("%s", str);
    printf("\n%s的专业数:%d\n", str, ChildCount(FindNode(t, str)));
    printf("%s的班级数:%d\n", str, LeafCount(FindNode(t, str)));
    printf("\n请输入学院名:");
    scanf("%s", str);
    printf("\n%s的学生数:%d\n", str, LeafSumOfvalue(FindNode(t, str)));
    printf("销毁树!\n");
    DestroyTree(t);
    return 0;
}